package com.sicheng.lc.lc笔试.美团篇;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/9/4 0:32
 */
public class 字母树 {
    /**
     * 给定一棵有n个节点的树，节点用1,2,…n编号。
     * 1号节点为树的根节点，每个节点上有一个用大写字母表示的标记。
     * 求每个节点的子树中出现的字母标记种类数。
     * 注：子树的定义：设T是有根树，a是T中的一个顶点，由a以及a的所有后裔（后代）导出的子图称为有根树T的子树。
     * 输入描述
     * 第一行输入一个正整数n，表示树的节点数量。
     * 第二行输入n-1个正整数，第i个整数表示第i+1号节点的父亲节点。
     * 第三行输入长度为n的由大写字母组成的字符串s1s2s3...sn，第i个字符si表示第i号节点的标记。
     * 3≤n≤50000.
     * 数据保证形成一棵合法的树，字符串由大写字母组成。
     * 输出描述
     * 输出n个整数，相邻两个数之间用空格隔开，第i个整数表示第i号节点的子树中出现不同的字母种类数。
     *
     * input:
     * 6
     * 1 2 2 1 4
     * ABCCAD
     *
     * output:
     * 4 3 1 2 1 1
     */
}
